import java.util.Arrays;

/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution31 {

    public static void main(String args[]) {
        Solution31 s = new Solution31();
        int[] num = new int[]{1, 3, 3};
        s.nextPermutation(num);
        System.out.println(Arrays.toString(num));
    }

    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int st = n - 2;
        while (st >= 0 && nums[st] >= nums[st + 1]) {
            st--;
        }
        if (st < 0) {
            reverse(nums);
            return;
        }
        if (st == n - 2) {
            swap(nums, n - 2, n - 1);
            return;
        }

        int minIdx = st + 1;
        for (int i = minIdx; i < n; i++) {
            if (nums[minIdx] >= nums[i] && nums[i] > nums[st]) {
                minIdx = i;
            }
        }
        swap(nums, minIdx, st);
        for (int i = 0; i < (n - st - 1) / 2; i++) {
            swap(nums, st + 1 + i, n - 1 - i);
        }
    }

    public void swap(int[] nums, int a, int b) {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }

    public void reverse(int[] nums) {
        for (int i = 0; i < nums.length / 2; i++) {
            int t = nums[i];
            nums[i] = nums[nums.length - i - 1];
            nums[nums.length - i - 1] = t;
        }
    }


}
